There are a number of known character compaction and generation schemes, which decrease the number of memory locations required to generate a given character set, with each having certain advantages and disadvantages. U.S. Pat. No. 3,999,167 to Ito et al discloses a method and apparatus for generating character patterns such as Kanji characters. According to the teachings of this patent every other dot element in the original character matrix is stored, thereby achieving a reduction of 1/2 in the required memory allocation for the character generator. It is to be appreciated, however, that there is still an appreciable amount of memory utilized for the generation of the Kanji characters according to Ito et al.
U.S. Pat. No. 3,936,664 to Sato discloses a character generator for generating Kanji characters, with a given Kanji character being broken down into a plurality of vectors, with the X and Y location, the angle, and the length of the vector being stored. The generated character, however, is only an approximation of the original character and, though a reduction of memory is achieved, the memory space required appears to be excessive.
U.S. Pat. No. 3,980,809 to Cook discloses a character generator, where a library of patterns is stored, wherein the pattern to be generated is compared with a table of reference patterns on an element by element comparison basis until the pattern to be generated is found.
U.S. Pat. No. 4,068,224 to Bechtle et al sets forth a symbol generating apparatus for generating symbols from data stored in a storage device, wherein symbols represented by black and white areas are stored in compressed form, with the symbol being divided into columns and rows, with row position values in each column for white/black and black/white transitions being stored for each column, and with the positional values being referred to a coordinate common to all columns.
U.S. Pat. No. 4,125,873 to Chesarek sets forth a display compress image refresh system utilizing a refresh memory store having coded image information segments representing a visual image which is stored in addressable locations.
U.S. Pat. No. 4,173,753 to Chou discloses an input system for a Sino-Computer characterized by dividing the Chinese characters into six basic strokes, i.e., horizontal, vertical, dot, dash, clockwise and counterclockwise, with each kind of stroke being given a corresponding designated numerical symbol, thereby, according to the exact stroke writing sequence of any character to give each character a spelling number to represent the character, to facilitate the input operation. There is, however, no teaching in Chou to utilize patterns having a plurality of length parameters, or to utilize an overlapping technique to enhance the compaction ratio of the system.
U.S. Pat. No. 3,830,965 to Beaudette sets forth apparatus and method for transmitting a bandwidth compressed digital signal representation of a visible image. A pictorial representation is scanned horizontally with the first line being encoded bit wise in a run-length code with the following lines being encoded with referenced to the reference line, utilizing bit wise redundancy coding. In essence, this is a bit wise run-length code with vertical redundancy.
U.S. Pat. No. 3,950,609 to Tanaka et al sets forth a fascimile system which utilizes one dimensional coding with no references being made to a previous line. A first code is generated when the signal components are entirely white, a second signal component is generated when the components are entirely black, and a third signal is generated when the signal components are a mixture of black and white.
U.S. Pat. No. 3,992,572 to Nakagome et al sets forth a system for coding two dimensional information on a bit comparison basis. The white information between characters is compressed, but the information, that is, the black elements, for the characters are not compressed.
U.S. Pat. No. 4,181,973 to Tseng, which is assigned to the assignee of the present invention sets forth a character compaction and generation method an apparatus for Kanji characters. A set of symbols is defined to represent different patterns which occur frequently in the Kanji character set, with there being 61 such symbols disclosed. The information stored for each sparse matrix representing a given character is comprised of each symbol (S) in the sparse matrix, its position (P), and its size parameter (Q), limited to 2 length parameters, if the symbol represents a family of patterns which differ only in size. The P, S and Q parameters are stored in three different read only memories (ROM's). The characters are reconstructed serially from the information stored in the P, S, and Q Rom's.
U.S. Pat. No. 4,286,329 to Goertzel et al, which is assigned to the assignee of the present invention sets forth a complex character generator in which the strokes, vectors and common patterns in a Kanji character are defined by symbols. The result is a sparse matrix representation of the original Kanji character image. Compaction is achieved by storing not the whole character image, but the information on the non zero element in the sparse matrix. The information on the non zero element contains the location P of the non zero element, the type of symbols S for the non zero element, and the size parameter Y of the pattern, where the size parameter is comprised of a plurality of length parameter which may include three or more length parameters. Whereas the complex character generator of Tseng referenced above, operates in a serial fashion such that a given pattern must be decoded and then written before the decoding process of the following pattern is achieved, the complex character generator of Goertzel et al operates in a parallel mode such that as one pattern is being written the following pattern is being decoded and so on. Further, greater compaction is achieved since length parameters having 1, 2 or 3 or more parameters are utilized. The encoding method allows overlapping of portions of two patterns, such that a further increase in compression is achieved.
According to the present invention, a complex character generator is set forth utilizing a byte-scan high speed data compression/decompression scheme which utilizes a two-dimensional byte run-length code. The scheme encodes/decodes the data in an integer multiple of bytes. Namely, an integer multiple of bytes of the data is encoded with one code word. Conversely, an integer multiple of bytes of the original data is generated by decoding of one single code word. Since the data is handled in bytes, and not in bits as in any other scheme, it is more naturally suited to modern digital electronics, either in hardware implementation or software implementation. This is partially responsible for the simple implementation, and fast performance, where the machine does not waste time in converting byte to bit and bit to byte. There is no need to manipulate the decompressed data to fit the byte boundary of a buffer memory. The format of the byte-scan may take two forms and fits for either a single raster scanning I/O or a multi-raster scanning I/O such as a multi-nozzle ink jet, multi-stylus wire or electro-erosion printer head, or even a multi-beam display.